package 复习.面试TOP101.栈堆队列;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class 滑动窗口的最大值 {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        //结果集
        ArrayList<Integer> list = new ArrayList<>();
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            while (!deque.isEmpty() && num[i] > deque.peekLast()){
                deque.pollLast();
            }
            deque.addLast(num[i]);
        }

        list.add(deque.peekFirst());

        for (int i = size; i < num.length; i++) {
            if(num[i - size] == deque.peekFirst()){
                deque.pollFirst();
            }
            while (!deque.isEmpty() && num[i] > deque.peekLast()){
                deque.pollLast();
            }
            deque.addLast(num[i]);
            list.add(deque.peekFirst());
        }
        return list;
    }
}
/*
public class 滑动窗口的最大值 {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<>();//用来返回对应的值
        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            while(!deque.isEmpty() && num[i] > deque.peekLast()) deque.pollLast();
            deque.addLast(num[i]);
        }

        res.add(deque.peekFirst());

        for (int i = size; i < num.length; i++) {
            //视情况而定
            //第一种就是像我这里折磨写，直接用对应的下标去进行比对
            //第二种就是用长度去进行比对，就是说size - deque.peekFirst() + 1
            if(num[i - size] == deque.peekFirst()){
                deque.pollFirst();
            }
            while(!deque.isEmpty() && num[i] > deque.peekLast()){
                deque.pollLast();
            }
            deque.addLast(num[i]);
            res.add(deque.peekFirst());
        }
        return res;
    }
}
 */